# Definition for singly-linked list.
from copy import copy


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2
        if l2 is None:
            return l1

        res = []
        while l1:
            res.append((copy(l1), 1))
            l1 = l1.next

        while l2:
            res.append((copy(l2), 2))
            l2 = l2.next

        ordered = sorted(res, key=lambda x: (x[0].val, x[1]))
        for i in range(1, len(ordered)):
            ordered[i - 1][0].next = ordered[i][0]
        return ordered[0][0]

    def mergeTwoLists2(self, l1: ListNode, l2: ListNode) -> ListNode:
        """
        递归解法
        :param l1:
        :param l2:
        :return:
        """
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists2(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists2(l1, l2.next)
            return l2


ll1 = ListNode(1, ListNode(2, ListNode(4)))
ll2 = ListNode(1, ListNode(3, ListNode(4)))
solution = Solution()
print(solution.mergeTwoLists(ll1, ll2).val)
